package com.atguigu.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreeDemo1 {

    public static void main(String[] args)
    {
      

        	//ҪĽ
            HeadNode1 root = new HeadNode1(2);
            HeadNode1 node2 = new HeadNode1(1);
            HeadNode1 node3 = new HeadNode1(3);
            // HeadNode1 node4 = new HeadNode1(4);
            // HeadNode1 node5 = new HeadNode1(5);
		
		//˵ֶöѧϰݹķʽ
		root.setLeft(node2);
		root.setRight(node3);
		// node3.setRight(node4);
		// node3.setLeft(node5);
         int n=2;
        
         List<HeadNode1> list= helper(1,n);
        
        for (int i=0;i<list.size();i++) {
          
            System.out.println(list.get(i).val);
            System.out.println("---");
        }
        
    }
    
     

    private static List<HeadNode1> helper(int start, int end) {
        List<HeadNode1> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        for (int val = start; val <= end; val++) {
            List<HeadNode1> left = helper(start, val - 1);
            List<HeadNode1> right = helper(val + 1, end);
            for (HeadNode1 l : left) {
                for (HeadNode1 r : right) {
                    HeadNode1 root = new HeadNode1(val);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }

    
}


class HeadNode1{
    public int val;
    public HeadNode1 left;
    public HeadNode1 right;

    public HeadNode1(int node1)
    {
       this.val=node1;
    }

    public void setLeft(HeadNode1 left)
    {
      this.left=left;
    }

    public void setRight(HeadNode1 left)
    {
      this.right=left;
    }
}